package leetcode.f1t100;

import java.util.ArrayList;
import java.util.List;

/**
 * 在N*N矩阵中放入棋子, 同行,同列, 左斜, 右斜都不可放置两个及以上, 统计有多少种方式
 * https://leetcode.com/problems/n-queens-ii/
 * @Author lichongxiao
 * @Date 2022/9/28 9:44
 */
public class Q52_NQueensCount {

    public static void main(String[] args) {
        System.out.println(new Q52_NQueensCount().totalNQueens(4));
    }

    public int totalNQueens(int n) {
        List<Queens> queensList = new ArrayList<>();
        return process(n,0,0,queensList);
    }

    /**
     * n*n的矩阵，到（i，j）位置选择是否放置皇后，queenList是已放置的皇后列表
     * @param n
     * @param i
     * @param j
     * @param queensList
     * @return
     */
    private int process(int n, int i, int j, List<Queens> queensList) {
        //前进一格后到末尾跳下一行
        if(j==n){
            i++;
            j=0;
        }
        // 有某一行未放置，则直接返回
        if(i>queensList.size()){
            return 0;
        }
        // 放入了所有皇后，返回1
        if(queensList.size()==n){
            return 1;
        }
        //走完所有格子，返回0
        if(i==n){
            return 0;
        }
        Queens queens = new Queens(i, j, n);
        boolean flag = false;
        for (Queens q : queensList) {
            flag = queens.attackTest(q);
            if(flag){
                break;
            }
        }
        int p1 = process(n,i,j+1,queensList);
        int p2 = 0;
        if(!flag){
            queensList.add(queens);
            p2 = process(n,i,j+1,queensList);
            queensList.remove(queens);
        }
        return p1+p2;
    }



    public class Queens {
        private int x;
        private int y;
        private int n;

        public Queens(int x, int y, int n) {
            this.x = x;
            this.y = y;
            this.n = n;
        }

        public boolean attackTest(Queens queens){
            return this.x == queens.x ||
                    this.y == queens.y ||
                    this.x + this.y == queens.x+queens.y ||
                    this.x -queens.x == this.y - queens.y;
        }
    }


}
